package bfsAndDfs

// BFS
func findMinHeightTrees(n int, edges [][]int) []int {
	if n == 1 {
		return []int{0}
	}

	var (
		// Adjacency table 无向图邻接表
		adjTable = make([][]int, n)
		// 存储度数为1的节点
		queue []int
		// 存储度数表
		degree = make([]int, n)
	)

	// 构建无向图的邻接表
	for _, info := range edges {
		adjTable[info[0]] = append(adjTable[info[0]], info[1])
		adjTable[info[1]] = append(adjTable[info[1]], info[0])
		degree[info[0]]++
		degree[info[1]]++
	}

	// 将度数为1的节点存入队列
	for i, v := range degree {
		if v == 1 {
			queue = append(queue, i)
		}
	}

	// bfs
	level := make([]int, 0)
	for len(queue) != 0 {
		level = make([]int, 0)
		n := len(queue)
		// 遍历每一层节点
		for i := 0; i < n; i++ {
			e := queue[0]
			queue = queue[1:]
			level = append(level, e)
			// 遍历邻接节点，度数-1，然后将新的度数为1的节点存入queue
			for _, v := range adjTable[e] {
				degree[v]--
				if degree[v] == 1 {
					queue = append(queue, v)
				}
			}
		}
	}
	return level
}
